Algorithims Heap Project

Hannah Butsko, Emma Horton, Arianne Pozzi, Matthew Wilcox

Purpose

  • Process Student Applications
  • Prioritize them based on various criteria
  • Make admission offers to most qualified/preferred candidates

Max Heap Implemenation

def max_heap(lst, value):
    lst.append(value)  # Add the new value to the end of the heap
    idx = len(lst) - 1  # Get the index of the newly added element

    # Moving the newly added element up the tree as long as it's greater
    # than its parent, maintaining the max heap property
    while idx > 0:
        parent_index = (idx - 1) // 2
        if lst[idx] > lst[parent_index]:
            lst[idx], lst[parent_index] = lst[parent_index], lst[idx]
            idx = parent_index
        else:
            break

Pop max heap implementation

def pop_max_heap(lst):
    # Checking if list is empty
    if not list:
        return "The array is empty"

    # Checking if there is only one element in the list
    if len(lst) == 1:
        return lst.pop()

    # Maximum element
    max_elem = lst[0]
    # Last element
    last = lst.pop()

    if lst:
        # Moving the last element to the root position
        lst[0] = last
        index = 0
        n = len(lst)

        # Restore the tree by bringing down the element
        while True:
            left = index * 2 + 1
            right = index * 2 + 2
            largest = index

            # Comparing the largest value to the left child
            if left < n and lst[largest] < lst[left]:
                largest = left

            # Comparing the largest value to the right child
            if right < n and lst[largest] < lst[right]:
                largest = right

            # Checking if largest index has been changed
            # No need to swap elements or call function recursively if largest element was not changed
            if largest != index:
                # Swapping the values of the parent with the largest element
                lst[largest], lst[index] = lst[index], lst[largest]
                index = largest
            else:
                break

    # Returning the maximum element that was removed
    return max_elem

Function that organizes student payload into a dictionary

We organized each student into a dictionary to use within the functions to retain all of the students data while assigning a priority

def student_data(name, student_type, computer_science, math, year, orientation_day, email, street, city, state, zip_code):
    return {"name": name,
            "student_type": student_type,
            "computer_science": computer_science,
            "math": math,
            "year": year,
            "orientation_day": orientation_day,
            "email": email,
            "Street Address": street,
            "City": city,
            "State": state,
            "ZIP Code": zip_code}

Prioritizing each student

def priority(payload, idx):
    lst_priority = [
        1 if payload["student_type"] == "Graduate" else 0,
        1 if payload["computer_science"] is True else 0,
        1 if payload["math"] is True else 0,
        payload["year"],  # Closer students are graduating - higher the priority
        -payload["orientation_day"],
        # Reversing the orientation day value to give priority to students that register earlier
        idx  # Unique identifier of each student
    ]

    return lst_priority

Processing each student and admitting by priority criteria

def process_admissions(payload):
    lst = []  #
    admitted_students = []  # Initialize a list for admitted students

    # Enumerating through student requests and prioritizing them
    for idx, student in enumerate(payload):
        priority_student = priority(student, idx)
        max_heap(lst, priority_student)  # Adding every priority to our max heap

    # Admitting students up to a limit 25 based on max heap priorities
    while len(admitted_students) < 25 and len(lst) > 0:
        _, computer_science, math, year, orientation_day, idx = pop_max_heap(lst)
        admitted_students.append(idx)

    return admitted_students

Making offers to admitted students if places become available

def make_offers(payload, admitted_students, dropouts):
    offers = []

    # Checking for admitted students who haven't dropped the class
    for idx, request in enumerate(payload):
        if idx in admitted_students and idx not in dropouts:
            offers.append(request)

    # Filling empty spots with the most qualified students
    while len(offers) < 25:
        # Checking for the next most qualified student who hasn't been previously admitted
        next_student = None
        for index, request in enumerate(payload):
            if index not in admitted_students and index not in dropouts:
                if next_student is None or priority(request, index) > priority(next_student, index):
                    next_student = request

        # If no more qualified students are available, break the loop
        if next_student is None:
            break

        # Marking the student as admitted and add them to the offers list
        admitted_students.append(payload.index(next_student))
        offers.append(next_student)

    return offers

Make a random fake data set of size n

Using the faker package we built a function to create random students to populate our school to test our functions in createing priority queues.

def random_student_admission(size=40):
    # Initialize Faker
    fake = Faker()
    # Create list of student_data dicts
    student_list = []
    for individual in range(0, size):
        name = fake.name()
        student_type = np.random.choice(['Undergraduate', 'Graduate', 'Auditor'])
        computer_science = np.random.choice([True, False])
        math = np.random.choice([True, False])
        year = np.random.randint(0, 5)
        orientation = np.random.randint(1, 6)
        fake_email = fake.free_email()
        fake_address = fake.street_address()
        fake_city = fake.city()
        fake_state = fake.state()
        fake_zip = fake.postcode()
        student_list.append(
            student_data(name, student_type, computer_science, math, year, orientation, fake_email, fake_address, fake_city, fake_state, fake_zip))

    return student_list

Create Admited Sutdents List

We first create a list of admited students. We select the size of our class and generate a random class of that size. In this case we do 38/

Create Admited Sutdents List

We then process them through admissions leaving us with a table of admitted students.

                 name   student_type  computer_science   math  year  \
0        Michael Gray        Auditor              True   True     2   
1        Joshua Silva       Graduate              True  False     2   
2      William Warren        Auditor             False   True     4   
3          Linda Long       Graduate             False  False     0   
4      Michelle Perez  Undergraduate             False  False     3   
5       Laurie Martin        Auditor             False  False     4   
6       Steven Martin       Graduate             False  False     2   
7           Beth Cole        Auditor             False   True     4   
8      Michael Parker        Auditor             False  False     4   
9        Zachary Hunt       Graduate             False   True     3   
10       Nathan Curry  Undergraduate              True  False     3   
11       Mary Merritt       Graduate              True   True     1   
12      Michaela Hunt  Undergraduate             False   True     4   
13     Andrew Collier        Auditor             False   True     4   
14   Kathleen Osborne       Graduate             False  False     4   
15        Robin Scott       Graduate              True  False     1   
16     Jessica Harper       Graduate             False  False     4   
17     Natalie Palmer       Graduate              True   True     2   
18      David Jackson  Undergraduate              True   True     4   
19      Justin Bender        Auditor             False  False     4   
20   Cheryl Gallagher        Auditor              True   True     4   
21  Katherine Barnett  Undergraduate             False  False     4   
22      Julia Goodwin       Graduate              True   True     4   
23         John Adams        Auditor              True  False     3   
24        Leslie Ryan       Graduate             False   True     2   

    orientation_day                       email  \
0                 2       awilliams@hotmail.com   
1                 3        jrussell@hotmail.com   
2                 4          andrew19@yahoo.com   
3                 2     michaelporter@yahoo.com   
4                 1            sara43@yahoo.com   
5                 3       scottbrewer@yahoo.com   
6                 2  kathleenwilson@hotmail.com   
7                 2       jacksongene@yahoo.com   
8                 2  wilsoncourtney@hotmail.com   
9                 4           emily47@yahoo.com   
10                3            jose61@gmail.com   
11                2   stephenreynolds@gmail.com   
12                5       patrick55@hotmail.com   
13                3        latoya27@hotmail.com   
14                2    tiffanyjones@hotmail.com   
15                1      ashleyparker@yahoo.com   
16                2      victoria66@hotmail.com   
17                4     stephanieruiz@gmail.com   
18                2     timothynewton@gmail.com   
19                5        browndavid@gmail.com   
20                5   brandonwilcox@hotmail.com   
21                3      katiesimmons@yahoo.com   
22                4    stacyhernandez@yahoo.com   
23                2   maldonadovickie@yahoo.com   
24                1        urodriguez@yahoo.com   

                     Street Address                 City          State  \
0       94868 Decker Light Apt. 664    West Jenniferfort   Rhode Island   
1                   101 Steven Fort             Berryton         Kansas   
2       390 Raymond Plains Apt. 980         North Daniel          Texas   
3       44288 Mason Trace Suite 689             Lowebury     Washington   
4                 36263 Harris Road       Christinamouth     New Mexico   
5                 67696 Wilson Port      Lake Kevinmouth     Washington   
6        3461 Julie Bypass Apt. 195             Markbury     New Mexico   
7                 318 Mcbride Wells       New Ashleytown       Delaware   
8     711 Nicholas Squares Apt. 302      East Amyborough      Louisiana   
9                      436 Fox Cove  North Christinaberg           Utah   
10              739 Elizabeth Mount        Coffeychester  Massachusetts   
11              04947 Mclean Divide           Robertfort       Arkansas   
12     4529 William Ports Suite 676     New Jenniferfurt         Oregon   
13     5689 Harry Harbors Suite 781    West Timothymouth        Montana   
14  5408 Keller Extensions Apt. 957         North Adrian     New Jersey   
15      00963 Smith Manors Apt. 601          Kaitlynstad           Ohio   
16     671 Jeffery Divide Suite 316              Amyfort      Minnesota   
17     6922 Serrano Curve Suite 318           Meghanland       Delaware   
18       006 Andrea Bridge Apt. 403       Lake Juliaberg   South Dakota   
19                301 Nancy Centers           East Jenny      Minnesota   
20                    3013 Alec Row    East Gregorymouth          Maine   
21     4672 Warner Parkway Apt. 004            New Shane        Vermont   
22                1814 Jasmine Mall         New Jonathan       Colorado   
23              85366 Bennett Lakes          Russellland       New York   
24                   7260 Hall Port     Port Edwardshire        Indiana   

   ZIP Code  
0     38792  
1     61093  
2     44429  
3     90235  
4     32027  
5     22521  
6     16693  
7     62282  
8     72344  
9     11253  
10    48061  
11    91087  
12    30280  
13    20272  
14    47989  
15    84066  
16    39208  
17    72240  
18    11581  
19    29138  
20    92676  
21    80367  
22    24609  
23    29973  
24    82904  

Simulating dropouts

We are now goint to simulate two students, {python} admitted_students[3]

dropouts = [admitted_students[3], admitted_students[17]]

Making offers if places become available

This is now the final class after we had 2 dropouts.

                 name   student_type  computer_science   math  year  \
0        Michael Gray        Auditor              True   True     2   
1        Joshua Silva       Graduate              True  False     2   
2          Linda Long       Graduate             False  False     0   
3      Michelle Perez  Undergraduate             False  False     3   
4       Laurie Martin        Auditor             False  False     4   
5       Steven Martin       Graduate             False  False     2   
6           Beth Cole        Auditor             False   True     4   
7      Michael Parker        Auditor             False  False     4   
8        Nathan Curry  Undergraduate              True  False     3   
9        Mary Merritt       Graduate              True   True     1   
10      Michaela Hunt  Undergraduate             False   True     4   
11     Andrew Collier        Auditor             False   True     4   
12   Kathleen Osborne       Graduate             False  False     4   
13        Robin Scott       Graduate              True  False     1   
14     Jessica Harper       Graduate             False  False     4   
15     Natalie Palmer       Graduate              True   True     2   
16      David Jackson  Undergraduate              True   True     4   
17      Justin Bender        Auditor             False  False     4   
18   Cheryl Gallagher        Auditor              True   True     4   
19  Katherine Barnett  Undergraduate             False  False     4   
20      Julia Goodwin       Graduate              True   True     4   
21         John Adams        Auditor              True  False     3   
22        Leslie Ryan       Graduate             False   True     2   
23   Timothy Espinoza  Undergraduate              True   True     2   
24    Scott Velasquez        Auditor              True   True     1   

    orientation_day                       email  \
0                 2       awilliams@hotmail.com   
1                 3        jrussell@hotmail.com   
2                 2     michaelporter@yahoo.com   
3                 1            sara43@yahoo.com   
4                 3       scottbrewer@yahoo.com   
5                 2  kathleenwilson@hotmail.com   
6                 2       jacksongene@yahoo.com   
7                 2  wilsoncourtney@hotmail.com   
8                 3            jose61@gmail.com   
9                 2   stephenreynolds@gmail.com   
10                5       patrick55@hotmail.com   
11                3        latoya27@hotmail.com   
12                2    tiffanyjones@hotmail.com   
13                1      ashleyparker@yahoo.com   
14                2      victoria66@hotmail.com   
15                4     stephanieruiz@gmail.com   
16                2     timothynewton@gmail.com   
17                5        browndavid@gmail.com   
18                5   brandonwilcox@hotmail.com   
19                3      katiesimmons@yahoo.com   
20                4    stacyhernandez@yahoo.com   
21                2   maldonadovickie@yahoo.com   
22                1        urodriguez@yahoo.com   
23                3            eric14@yahoo.com   
24                1         suzanne48@gmail.com   

                     Street Address               City          State ZIP Code  
0       94868 Decker Light Apt. 664  West Jenniferfort   Rhode Island    38792  
1                   101 Steven Fort           Berryton         Kansas    61093  
2       44288 Mason Trace Suite 689           Lowebury     Washington    90235  
3                 36263 Harris Road     Christinamouth     New Mexico    32027  
4                 67696 Wilson Port    Lake Kevinmouth     Washington    22521  
5        3461 Julie Bypass Apt. 195           Markbury     New Mexico    16693  
6                 318 Mcbride Wells     New Ashleytown       Delaware    62282  
7     711 Nicholas Squares Apt. 302    East Amyborough      Louisiana    72344  
8               739 Elizabeth Mount      Coffeychester  Massachusetts    48061  
9               04947 Mclean Divide         Robertfort       Arkansas    91087  
10     4529 William Ports Suite 676   New Jenniferfurt         Oregon    30280  
11     5689 Harry Harbors Suite 781  West Timothymouth        Montana    20272  
12  5408 Keller Extensions Apt. 957       North Adrian     New Jersey    47989  
13      00963 Smith Manors Apt. 601        Kaitlynstad           Ohio    84066  
14     671 Jeffery Divide Suite 316            Amyfort      Minnesota    39208  
15     6922 Serrano Curve Suite 318         Meghanland       Delaware    72240  
16       006 Andrea Bridge Apt. 403     Lake Juliaberg   South Dakota    11581  
17                301 Nancy Centers         East Jenny      Minnesota    29138  
18                    3013 Alec Row  East Gregorymouth          Maine    92676  
19     4672 Warner Parkway Apt. 004          New Shane        Vermont    80367  
20                1814 Jasmine Mall       New Jonathan       Colorado    24609  
21              85366 Bennett Lakes        Russellland       New York    29973  
22                   7260 Hall Port   Port Edwardshire        Indiana    82904  
23                144 Jacob Village        Charlesfort         Alaska    37190  
24               06086 Leslie Cliff    North Tylerport      Tennessee    19390  

Power BI Implementation

Power Bi - Data Model

Power Bi - Not Admitted Students

Power Bi - Admitted Students

Power Bi - Acceptance email